Pencapaian Fernandes yang terbesar ialah pemulihan syarikat AirAsia sebagai sebuah syarikat penerbangan antarabangsa. Sebelum beliau memasuki perindustrian ini, negara-negara di Wilayah Asia Tenggara Selatan tidak mempunyai sebarang persetujuan Langit Terbuka. Pada pertengahan 2003, Fernandes telah meminta Dr. Mahathir untuk mengemukakan cadangan persetujuan itu kepada negara Thailand, Indonesia dan Singapura. Atas permintaanya, beliau mencapai kejayaaan dalam mendapat hak pendaratan, bukan sahaja untuk AirAsia, tetapi juga untuk syarikat-syarikat penerbangan tambang rendah yang lain.

Ferdandes juga berjaya merevolusikan perindustrian penerbangan serantau melalui penerbangan tambang rendah. Sekarang, terdapat beberapa syarikat penerbangan tambang rendah di wilayah ini, iaitu:

• Tiger Airways, sebuah syarikat Singapura yang dimiliki oleh Singapore Airlines;
• Penggabungan syarikat Valuair dari Singapura, dengan JetStar yang dimiliki oleh Qantas Airways dari Australia;
• Nok Air, sebuah syarikat Thailand; dan
• Lion Air, sebuah syarikat Indonesia.

Fernandes telah menerima banyak anugerah, termasuknya:

• "Siri Pengkhayal-Pengkhayal dan Kepimpinan" (Visionaries & Leadership Series) oleh International Herald Tribune, sebuah syarikat akhbar di Amerika Syarikat, bagi kerjanya yang cemerlang di syarikat AirAsia;
• "Ketua Syarikat Malaysia bagi Tahun 2003" (Malaysian CEO of the Year 2003) pada Disember, 2003 — sejenis anugerah tertinggi yang sehingga kini, hanya diberikan kepada sembilan pengusaha di Malaysia oleh American Express dan Business Times. Anugerah ini diberikan kepada Fernandes bagi mengakui prestasi pengusahaan dan kemahiran pengurusannya di kalangan pemimpin-pemimpin syarikat-syarikat Malaysia;
• "Pengusaha Baru Malaysia Yang Terutama Bagi Tahun 2003" (Emerging Entrepreneur of the Year - Malaysia 2003) pada tahun 2004;
• "25 Bintang Asia" (25 Stars of Asia) oleh Business Week pada tahun 2005.
• 2010 Forbes Asia businessman of the year[34]
• 2011 No. 52, in FastCompany Top 100 Most Creative People in Business.[35]
• "Brand Builder of the Year" 2014 di World Branding Awards, untuk kerjanya dalam membina jenama AirAsia[36]